package com.cat.graphTheory;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/all-paths-from-source-to-target/
 * @create 2025/9/18 20:01
 * @since JDK17
 */

public class Solution02 {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    int n;
    int[][] g;
    void dfs(int cur) {
        list.add(cur);
        if (cur == n - 1) {
            ans.add(new ArrayList<>(list));
        }
        for (int x : g[cur]) {
            dfs(x);
        }
        list.remove(list.size() - 1);
    }

    public List<List<Integer>> allPathsSourceTarget(int[][] graph) {
        n = graph.length;
        g = graph;
        dfs(0);
        return ans;
    }
}
